[Coding027] Sort - 词典排序

Lexicographic-sort

More coding records

Get the knowledge flowing and circulating! :)

目录

标题：词典排序

Words & phrases

lexicographic 美/ ˌleksɪkəˈɡræfɪk /

• adj.词典编辑的；字典式的

Lexicographic order is imposed on the namespace declarations and attributes of each element.

对名称空间声明和每个元素中的属性采用词典序。

字典序是指按照单词首字母顺序在字典中进行排序的方法。在数学中可推广到有序符号序列，可视为完全有序集合的元素序列的一种排序方法。

概念

在英文字典中，排列单词的顺序是先按照第一个字母以升序排列（即a、b、c……z 的顺序）；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，sigh 和 sight），那么把短者排在前。

通过这种方法，我们可以给本来不相关的单词强行规定出一个顺序。“单词”可以看作是“字母”的字符串，而把这一点推而广之就可以认为是给对应位置元素所属集合分别相同的各个有序多元组规定顺序。

形式定义

给定两个偏序集 $A$$A$ 和 $B$$B$ ，$(a,b)$$(a, b)$ 和 $(a^{\prime },b^{\prime })$$(a', b')$ 属于笛卡尔积 $A\times B$$A \times B$，则字典序定义为

$$(a,b)\le (a^{\prime },b^{\prime })\text{当}\text{且}\text{仅}\text{当}a<a^{\prime }\text{或}(a=a^{\prime }\text{且}b\le b^{\prime }).$$

结果是偏序。如果 $A$$A$ 和 $B$$B$ 是全序, 那么结果也是全序。

——维基百科

• Let $C_i$$C_i$ be the comparator that compares two tuples by their $i$$i$-th dimension i.e.

  • for $C_2$$C_2$:

    $$(x1,x2,x3)\le (y1,y2,y3)ifx2\le y2$$

  • for $C_3$$C_3$:

    $$(x1,x2,x3)\le (y1,y2,y3)ifx3\le y3$$

• Let stableSort(S, C) be any stable sorting algorithm that uses comparator $C$$C$

• Lexicographic-sort sorts a sequence of $d$$d$-tuples in lexicographic order by executing $d$$d$ times algorithm stableSort, one per dimension

实例

sort according to left-most dimension

• (2, 1, 4) (3, 2, 4) (5, 1, 5) (7, 4, 6) (2, 4, 6)

• (2, 1, 4) (5, 1, 5) (3, 2, 4) (7, 4, 6) (2, 4, 6)

• (2, 1, 4) (2, 4, 6) (3, 2, 4) (5, 1, 5) (7, 4, 6)

注意

Notice that the sorting goes from last to first. Why?

Lexicographic-sort runs in $O(dT(n))$$O(dT(n))$ time, where $T(n)$$T(n)$ is the running time of stableSort.

辨析

lexicographical order：字典顺序：一种排序方法，按照字母表顺序排列单词或字符串。

numerical order：数字顺序：按照数字大小或顺序排列的顺序。

alphabetical order：按字母顺序排列：一组项目（例如字典中的单词）按照字母顺序排列的顺序。

Demo

• lexicographical order: 1, 10, 2

• numerical order: 1, 2, 10

• alphabetical order: 1, 10, 2